package com.hy.treeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeNodeMinDepth {


    /**
     * 111.二叉树的最小深度
     * 力扣题目链接
     *
     * 相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。
     *
     * 需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
     * 思路：
     * 使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
     * 在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

     *
     * @param root
     * @return
     */
    public int getTreeNodeMinDepth(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null){
            return 0;
        }
        deque.offerLast(root);
        int depth = 0;
        while (!deque.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int len = deque.size();
            depth ++;
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.pollFirst();
                temp.add(node.val);
                // 如果当前节点的左右孩子都为空，直接返回最小深度
                if (node.left == null && node.right == null){
                    return depth;
                }
                if (node.left != null){
                    deque.offerLast(node.left);
                }
                if (node.right != null){
                    deque.offerLast(node.right);
                }
            }
        }
        return depth;
    }

    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeMinDepth treeNodeSearch = new TreeNodeMinDepth();

        System.out.println("二叉树最小的深度 : "+ treeNodeSearch.getTreeNodeMinDepth(root));
    }
}
